package com.gozap.sort.algorithm;

import com.gozap.sort.data.SortData;

/**
 * 快速排序具体排序算法实现（将数组分为两部分，前半部分都小于指定值，后半部分都大于指定值）
 * 
 * @author yaoming
 * @date 2013-1-4 下午05:07:04
 * @since JDK1.6
 * @version 2.0.0
 */
public class QuickSort implements Sort{

	private SortData data;
	
	public void sort(){
		quickSort(0, data.length()-1);
	}

	/**
	 * 将数据分为两部分,一部分大于key值,一部分小于key值,返回key值的下标
	 * 
	 * @param arr
	 * @param begin
	 * @param end
	 * @return
	 */
	private int partion(int begin, int end) {
		int index = begin;

		for (int j = begin; j < end; j++) {
			if (data.compare(end, j)) {
				data.swap(index, j);
				index++;
			}
		}
		data.swap(index, end);
		return index;
	}

	/**
	 * 快速排序
	 * 
	 * @param arr
	 * @param begin
	 *            起始的下标(包括此下标)
	 * @param end终点的下标
	 *            (包括此下标)
	 */

	public void quickSort(int begin, int end) {
		if (end > begin) {
			int part = partion(begin, end);
			if (part == end) {
				quickSort(begin, part - 1);
				quickSort(part, end);
			} else {
				quickSort(begin, part);
				quickSort(part + 1, end);
			}

		}
	}

	public SortData getSortData() {
		return data;
	}

	public void setSortData(SortData data) {
		this.data = data;
	}

}
